package class13;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class PrintAllPermutations2 {

    public static void swap(char[] str,int i,int j){
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }

    public static List<String> permutation1(String s){
        List<String> ans = new ArrayList<>();
        char[] str = s.toCharArray();
        if (s == null || s.length() == 0){
            return ans;
        }
        process1(str,0,ans);
        return ans;
    }

    public static void process1(char[] str,int index,List<String> ans){
        if (index == str.length){
            ans.add(String.valueOf(str));
            return;
        }
        for (int i = index;i<str.length;i++){
            swap(str,index,i);
            process1(str,index+1,ans);
            swap(str,index,i);
        }
    }

    public static List<String> permutation2(String s){
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0)
            return ans;
        char[] str = s.toCharArray();
        process2(str,0,ans);
        return ans;
    }

    public static void process2(char[] str,int i,List<String> res){
        if (i == str.length){
            res.add(String.valueOf(str));
            return;
        }
        boolean[] visit = new boolean[26];
        for (int j = i;j<str.length;j++){
            if (!visit[str[j] - 'a']){
                visit[str[j] -'a'] = true;
                swap(str,i,j);
                process2(str,i+1,res);
                swap(str,i,j);
            }
        }
    }

    public static void main(String[] args) {
        String s = "acc";
        List<String> ans1 = permutation1(s);
        for (String str : ans1) {
            System.out.println(str);
        }
        System.out.println("=======");
        List<String> ans2 = permutation2(s);
        for (String str : ans2) {
            System.out.println(str);
        }
    }
}
